LEE CHANWOO

📝 Blog 2024 version 1.6.1
🔖 NOV 1, 2024

10 분 소요

image


Process Scheduling


MultiProgramming (Multi-tasking)

  • Multiple processes in the system with one or more processors
  • Increases processor utilization by organizing processes so that the processor always has one to execute


  • Resource management
    • Resources for time sharing
      • Multiple processes use a resource in a time-shared manner
      • Processor
      • Process scheduling
        • Allocates processor time slots to processes
    • Resources for spacing sharing
      • Partition a resource and let each process use the partitions allocated to him
      • Memory


Goals of Scheduling


Goals of process scheduling

  • Improving system performance while caring for each process

Typical performance indices

  • Response time
  • Throughput
  • Resource utilization
  • Turnaroud time
  • Predictability
  • Fairness
  • Etc

Each system selects a scheduling policy with the consideration on the performance indices for its application domain


  • Mean response time
    • The amount of time it takes to start responding
      • Time from the submission of a request until the first response is produced
    • Used in interactive systems
  • Throughput
    • The number of processes completed per time unit
    • Used in batch systems
  • Resource utilization
    • Percentage of time that the resource is busy during a given interval
    • Used in batch systems
  • Turnaroud time
    • Interval from the time of submission to the time of completion
  • Waiting time
    • Sum of the periods spent waiting in the ready queue
  • Predictability
  • Fairness
  • Etc


Scheduling Level

  • Long-term scheduling
  • Medium-term scheduling
  • Short-term scheduling


image


Long-term scheduling

  • Job scheduling, admission scheduling, high-level scheduling
  • Selects the jobs to be submitted into the system and registered to the kernel
    • Controls multiprogramming degree
    • Should select a good process mix of I/O-bound and compute-bound processes
  • In most time-sharing systems, each job or command is put into the system immediately after its submission
    • No long-term scheduling


Medium-term scheduling

  • Intermediate-level scheduling
  • Memory allocation
    • Swapping (swap-in/swap-out)
  • Dependent on memory management schemes of the operating systems


Short-term scheduling

  • Process scheduling, low-level scheduling
  • Selects a process among the processes that are ready to execute, and allocates CPU to him
  • Process scheduler, dispatcher
    • Executed when interrupt occurs or when the running process makes a system call and incurs a context switch
  • Should select a new process for CPU frequently
    • Assume 100ms average CPU burst and 10ms for the scheduling decision
    • 10 / (100+10) = 9% of the CPU is being used simply for scheduling


Scheduling Policies


Preemptive scheduling

  • CPU may be preempted to another proecss independent of the intention of the running process
    • Flexibility, adptability, performance improvements
  • Used for time-sharing systems and real-time systems
  • Incurs a cost associated with access to shared data $\rightarrow$ [Process synchronization]
  • Affects the design of operating system kernel
    • Kernel data integrity and consistency
  • High context switching overhead

image


Non-preemptive scheduling

  • Process uses the CPU until it voluntarily releases it (eg. for system call)
  • No preemption
  • Pros
    • Low context switch overhead
  • Cons
    • Frequent priority inversions
    • May result in longer mean response time

image


Priority

  • Classification
    • Static priority (external priority)
      • Decided at process creation time and fixed during execution of the process
      • Not adaptable to system environments
      • Simple, low-overhead
    • Dynamic priority (internal priority)
      • Initial priority at process creation time
      • May vary as the state of the system and processes changes
      • Adaptable to system environments
      • Complex, high overhead doe to priority adjustment


Terminologies

CPU burst vs I/O burst

  • Process execution consists of a cycle of CPU execution and I/O wait
  • CPU burst
    • Each cycle of CPU execution
  • I/O burst
    • Each cycle of I/O wait
  • Burst time is an important factor(criteria) for scheduling algorithms

image


Scheduling Schemes

  • FCFS
  • RR
  • SPN
  • SRTN
  • HRRN
  • Priority
  • MLQ
  • MFQ


FCFS (First-Come-First-Service) scheduling

  • Non-preemptive scheduling
  • Scheduling criteria
    • Arrival time (at the ready queue)
    • Faster arrival time process first
  • High resource utilization
  • Adequate for batch systems, not for interactive systems
  • Disadvantages
    • Convoy effect
      • Many processes may wait for one big process to get off the CPU
    • Longer mean response time

image


image


RR (Round-Robin) scheduling

  • Preemptive scheduling
  • Scheduling criteria
    • Arrival time (at the ready queue)
    • Faster arrival time process first
  • Time quantum for each process
    • System parameter
    • The (running) process that has exhausted his time quantum releases the CPU and goes to the ready state (timeout)
      • Prevents monopoly of the CPU by a process
  • High context switching overhead due to preemptions
  • Adequate for interactive/time-sharing system
  • Performance of the RR scheme depends heavily on the size of the time quantum
    • Very large (infinite) time quantum $\rightarrow$ FCFS
    • Very small time quantum $\rightarrow$ processor sharing
      • Appears to the users as though each of the n processes has its own processor running at 1/n speed of the real processor

image


image


SPN (Shortest-Process-Next) scheduling

  • SJF(Shortest Job First) scheduling
  • Non-preemptive scheduling
  • Scheduling criteria
    • Burst time
    • Shortest next CPU burst time first scheduling
  • Pros
    • Gives minimum average waiting time for a given set of processes
    • Minimizes the number of processes in the system
      • Reduces the size of the ready queue
      • Reduces the overall space requirements
    • Fast responses to many processes
  • Cons
    • Starvation, indefinite postponement(blocking)
      • Long burst-time processes
      • Can be solved by *aging
    • No way to know the length of the next CPU burst for each process
      • It is necessary to have a scheme for burst time estimation
      • Estimation by exponential average
        • $\tau_{n+1} = \alpha t_n + (1-\alpha) \tau_n = \alpha t_n + (1-\alpha)\alpha t_{n-1} + \dots + (1-\alpha)^j \alpha t_{n-j} + \dots + (1-\alpha)^{n+1} \tau_0$
        • $t_n$ : Length of the n-th CPU burst
        • $\tau_0$ : Constant
        • $0 \leq \alpha \leq 1$


image


SRTN (Shortest Remaining Time Next) scheduling

  • Variation of SPN scheduling (preemptive SPN)
  • Preemptive scheduling
    • Preempt current running process when another process with shorter remaining CPU burst time arrives at the ready queue
  • Cons
    • Burst time estimation overhead as in SPN
    • Overhead for tracing remaining burst time
    • High context switching overhead


image


HRRN (High-Response-Ratio-Next) scheduling

  • Uses aging concepts
    • Give chances to long burst time processes
  • Scheduling criteria
    • Higher response-ratio process first
  • Response ratio
    • Length of waiting time relative to that of burst (service) time


image


  • Prevents starvation
    • Increase the priority of the process that waits on the ready queue
    • Aging
  • Similar effects as SPN scheduling
  • Cons
    • Burst time estimation overhead as in SPN


Priority scheduling

  • Scheduling criteria
    • Process priority
    • Tie breaking: FCFS
  • Priority in real operating systems
    • Priority range is different for each system
    • Mapping from the numerical value of the priority to the priority level is different for each system
  • Can be either preemptive or non-preemptive
  • Major problem
    • Starvation


image


MLQ(Multi-level Queue) scheduling

  • Partitions the ready queue into multiple separate queues
  • Processes are permanently assigned to one queue based on some properties of the process
  • Each queue has its own scheduling mechanism
  • Scheduling among the queues
    • Generally, fixed-priority preemptive scheduling


image


MFQ(Multi-level Feedback Queue) scheduling

  • Can be used without any information on processes
    • Arrival time, burst time, etc
  • Multiple ready queues as in MLQ
  • Goals of MFQ scheduling
    • Favor short burst-time processes
      • Favor I/O bound processes
    • Improved adaptability
  • Feedback
    • The processor usage pattern of the process
    • Multi-level feedback queue
      • Allows processes to move among the ready queues in the system
  • Characteristics of MFQ scheduling
    • Dynamic priority
    • Preemptive scheduling
    • Favor short burst-time processes
      • Favor I/O-bound processes
    • Improved adaptability
    • Effects of SPN, SRTN, and HRRN schemes can be get without any information on the processes


image


  • Scheduling mechanism
    • New process goes into $RQ_0$
    • When a running process dispatched from $RQ_i$ goes to sleep for IO, it returns back to $RQ_i$ when it wakes up
    • When a running process dispatched from $RQ_i$ is preempted, it goes to $RQ_{i+1}$
    • A process dispatched from $RQ_n$ returns to $RQ_n$ in any case


  • Variations of MFQ scheduling
    • Problems of MFQ scheduling
      • High overhead
      • Starvation of the processes at low priority queues
    • Variations of MFQ scheduling


image


  • Parameters for MFQ scheduling
  • The number of queues
  • The scheduling algorithm for each queue
  • The method used to determine when to upgrade a process to a higher-priority queue
  • The method used to determine when to demote a process to a lower-priority queue
  • The method used to determine which queue a process will enter when that process needs service


Case Studies

  • Unix
  • Windows OS
  • Linux


Unix

  • Interactive system
    • Priority-based scheduling
  • Priority
    • Kernel priority
      • Priority of the processes in kernel mode
      • Interruptible/uninterruptible priority
    • User priority
      • Priority of the processes in user mode
  • Clock handler
    • Interrupts processor periodically, when the kernel adjusts the priorities of all processes in the system

image


Scheduling in Unix Systems

  • Scheduling principles
    • Dispatch higher priority process first
    • Priority of the processes
      • Varies as it uses the processor
    • Similar to MFQ algorithm
  • Scheduling mechnism
    • Priority adjustment

image


image


Scheduling in Unix Systems : FSS

  • FSS
    • Fiar shar scheduling
  • Principle
    • Divide the usr community into a set of fair share groups
    • System allocates it CPU time proportionally to each group
  • Implementation
    • Each process has a new field in its u-area that points to a fair share CPU usage field, shared by all processes in the fair share group

image


Windows

  • Thread scheduling
  • Priority-based, preemptive scheduling
  • 32-level priority scheme
    • Variable class: 1-15
    • Real-time class: 16-32
  • The dispatcher uses a queue for each scheduling priority, and traverses the set of queues from highest to lowest until it finds a thread that is ready to run


  • Priority classes
    • REALTIME_PRIORITY_CLASS
    • HIGH_PRIORITY_CLASS
    • ABOVE_NORMAL_PRIORITY_CLASS
    • NORMAL _PRIORITY_CLASS
    • BELOW_NORMAL _PRIORITY_CLASS
    • IDLE _PRIORITY_CLASS


  • Relative priorities in each class
    • TIME_CRITICAL
    • HIGHEST
    • ABOVE_NORMAL
    • NORMAL
    • BELOW_NORMAL
    • LOWEST
    • IDLE

image


  • Scheduling scheme
    • When a thread’s time quantum runs out, its priority is lowered (if it is in the variable priority class)
    • When a variable priority thread is released from a wait operation, the dispatcher boosts the priority
      • The boost of amount depends on what the thread was waiting for
        • Keyboard or mouse I/O $\rightarrow$ large increase
        • Disk I/O $\rightarrow$ moderate increase
    • When a process moves into the foreground, the scheduling quantum may be increased by the factor of 3
  • Scheduling in Windows 7
    • UMS (User-Mode Scheduling)
      • Allows applications to create and manage threads independently of the kernel (Applications can create and schedule multiple threads without involving the Windows kernel scheduler)
      • More efficient than kernel-mode thread scheduling (Due to no kernel intervention)
      • Schedulers in libraries on top of UMS
        • Eg) ConcRT (Concurrency Runtime)
          • Provides user-mode scheduler with facilities for parallelism
          • Designed for task-based parallelism on multi-core processors


Linux

  • Up to version 2.4
    • Used a variation of traditional Unix scheduling algorithm
      • Priority-based scheduling and round-robin scheduling
      • Multilevel feedback queue
    • Two problems
      • No adequate support for SMP systems
      • No scalability (in scheduling) for the number of tasks


  • Version 2.4~2.6.22
    • O(n) and O(1) scheduling
    • SMP support
      • Processor affinity
        • Keep a task running on the same processor
        • Avoid the cost of invalidating and repopulating caches
      • Load balancing
    • Fairness
    • Ideal for large server workloads
    • Performed below par on desktop systems with interactive applications


  • Version 2.6.23~
    • Modular scheduler
      • Scheduler classes
        • Enable different, pluggable algorithms to coexist, scheduling their own types of processes
    • CFS(Completely Fair Scheduler)
    • Implementation of a well-studied, classic scheduling algorithm, called fair queuing(fair scheduling)
      • Uses red-black trees
    • Improvement in interactive performance of the scheduler
    • O(logN) scheduling
      • N: number of tasks in the runqueue (red-black tree)


Linux scheduler

  • I/O-bound processes vs CPU-bound processes
    • Tries to optimize process response (thus favoring I/O-bound processes) in a creative manner that does not neglect CPU-bound processes
  • Preemptive priority-based scheduling
    • Numerically lower values indicate higher priorities
  • Two separate priority ranges
    • Real-time range: 0-99
    • Nice value range: 100-139


-Scheduler classes -A specific priority for each class -Different scheduling algorithm for each scheduler class -Typical two scheduling classes - Default scheduling class - CFS scheduling algorithm - Real-time scheduling class - Another algorithm -New scheduling classes can be added


  • Priority ranges
    • Real-time range
      • 0~99
      • SCHED_FIFO, SCHED_RR
    • Non-real-time (Nice value) range
      • 100~139
      • SCHED_OTHER

image


  • Real-time scheduling as defined by POSIX.1b
  • Priority assignment
    • Real-time tasks
      • Assigned static priorities
    • All other tasks
      • Assigned dynamic priorities based on their nice values plus/minus the value 5
      • Adjustment of [-5,+5] is determined by the interactivity of the task
      • Longer sleep time → more I/O-bound → more interactive


  • Scheduling data structures
  • Each processor maintains its own runqueue data structure and schedules itself independently

image


Multiple Procsseer Scheduling

  • Issues for multicore architecture
    • Multicore processors
      • Multiple processor cores on the same physical chip
      • Each core has a register set
        • Appears to the OS to be a separate physical processor
    • Scheduling for multithreaded multicore processor
      • 2 steps
        • Assignments of threads for each core
        • Selection of a thread to run on each core
    • Issues
      • Processor affinity
      • Load balancing


Issues

  • Processor affinity
    • Avoid migration of processes from one processor to another and attempt to keep a process on the same processor
      • To reduce the cost of invalidating and repopulating caches
    • Soft affinity
      • Attempts to keep a process on the same processor, but does not guarantee it
    • Hard affinity
      • No migration of processes
      • Linux has system calls that support hard affinity
  • Load balancing
    • Attempts to keep the workload evenly distributed across all processors in the system
    • Push migration
      • A specific task that monitors the load on each processor
      • When it finds imbalance
        • Evenly distributes the load by moving (pushing) processes from overloaded to underloaded processors
    • Pull migration
      • Idle processor pulls a waiting processes from a busy processors
    • Usually push and pull migration schemes are used in parallel on load-balancing systems
      • [ex] Linux scheduler
        • Push migration every 200ms
        • Pull migration whenever runqueue for a processor is empty


Real-time Scheduling

  • Priority-based scheduling
  • RM(Rate-Monotonic) scheduling
    • Static priority
  • EDF(Earliest-Deadline-First) scheduling
    • Dynamic priority


Summary

  • Process scheduling
    • Goals of process scheduling
    • Scheduling level
    • Scheduling criteria
  • Scheduling algorithms
  • Case study
    • Unix, Windows OS, Linux
  • Multicore processor scheduling & Real-time scheduling

댓글남기기

참고